// 1. 最大子数组
fn find_max_crossing_subarray(
    v: &Vec<i8>,
    low: usize,
    mid: usize,
    high: usize,
) -> (usize, usize, i8) {
    println!(
        "cross_find------\nlow: {}, mid: {}, high: {}\n----------",
        low, mid, high
    );
    let mut left_sum = i8::MIN;
    let mut sum = 0;
    let mut max_left = mid;
    for i in (low..=mid).rev() {
        sum += v[i];
        if sum > left_sum {
            left_sum = sum;
            max_left = i;
        }
    }

    let mut right_sum = i8::MIN;
    sum = 0;
    let mut max_right = mid + 1;
    for i in (mid + 1)..=high {
        sum += v[i];
        if sum > right_sum {
            right_sum = sum;
            max_right = i;
        }
    }

    (max_left, max_right, left_sum + right_sum)
}

pub fn find_maximum_subarray(v: &Vec<i8>, low: usize, high: usize) -> (usize, usize, i8) {
    println!("low: {}, high: {}", low, high);
    if high == low {
        return (low, high, v[low]);
    } else {
        let mid = (((low + high) / 2) as f32).ceil() as usize;

        let (left_low, left_high, left_sum) = find_maximum_subarray(&v, low, mid);
        let (right_low, right_high, right_sum) = find_maximum_subarray(&v, mid + 1, high);
        let (cross_low, corss_high, cross_sum) = find_max_crossing_subarray(&v, low, mid, high);

        if left_sum >= right_sum && left_sum >= cross_sum {
            return (left_low, left_high, left_sum);
        } else if right_sum >= left_sum && right_sum >= cross_sum {
            return (right_low, right_high, right_sum);
        } else {
            return (cross_low, corss_high, cross_sum);
        }
    }
}

// 2. 最大子数组---暴力求解
pub fn find_maximum_subarray_violence(v: Vec<i8>) -> (usize, usize, i8) {
    let mut sum;
    let mut max_sum = i8::MIN;
    let mut min_index = 0;
    let mut max_index = 0;
    for i in 0..v.len() {
        sum = 0;
        for j in i..v.len() {
            sum += v[j];
            if sum > max_sum {
                max_sum = sum;
                min_index = i;
                max_index = j;
            }
        }
    }
    (min_index, max_index, max_sum)
}

// 3. 最大子数组---非递归-线性时间
pub fn find_maximum_subarray_non_recursive(v: Vec<i8>) -> (usize, usize, i8) {
    let mut max_sum = v[0];
    let mut min_index = 0;
    let mut max_index = 0;
    let mut temp_sum;
    let mut temp_min_index = 0;
    for i in 1..v.len() {
        println!("i: {}", i);
        temp_sum = i8::MIN;
        let mut temp = 0;
        for j in (0..=i).rev() {
            temp += v[j];
            if temp > temp_sum {
                temp_sum = temp;
                temp_min_index = j;
            }
        }
        if temp_sum > max_sum {
            max_sum = temp_sum;
            min_index = temp_min_index;
            max_index = i;
        }
        println!(
            "min_index: {}, max_index: {}, max_sum: {}",
            min_index, max_index, max_sum
        );
    }
    (min_index, max_index, max_sum)
}

// 4. 矩阵乘法--直接法
pub fn square_matrix_multiply(a: Vec<Vec<i32>>, b: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = a.len();
    let mut c = vec![vec![0; n]; n];
    for i in 0..n {
        for j in 0..n {
            c[i][j] = 0;
            for k in 0..n {
                c[i][j] = c[i][j] + a[i][k] * b[k][j];
            }
        }
    }
    c
}

// 5. 矩阵乘法--直接的递归分治算法
pub fn square_matrix_multiply_recursive(
    a: &Vec<Vec<i32>>,
    b: &Vec<Vec<i32>>,
    row: ((usize, usize), (usize, usize)),
    column: ((usize, usize), (usize, usize)),
) -> Vec<Vec<i32>> {
    let n = row.0 .1 - row.0 .0;
    let mut c = vec![vec![0; n + 1]; n + 1];

    if n == 0 {
        c[0][0] = a[row.0 .0][column.0 .0] * b[row.1 .0][column.1 .0];
        // println!("----------------------");
        // println!("A[{}][{}] * B[{}][{}]", row.0 .0, column.0 .0, row.1 .0, column.1 .0);
        // println!("{} * {} = {}", a[row.0 .0][column.0 .0], b[row.1 .0][column.1 .0], c[0][0]);
    } else {
        println!(
            "A[{}..{}][{}..{}] * B[{}..{}][{}..{}]\n",
            row.0 .0,
            row.0 .1,
            column.0 .0,
            column.0 .1,
            row.1 .0,
            row.1 .1,
            column.1 .0,
            column.1 .1
        );
        let a_row_mid = (row.0 .0 + row.0 .1 + 1) / 2 - 1;
        let a_column_mid = (column.0 .0 + column.0 .1 + 1) / 2 - 1;

        let b_row_mid = (row.1 .0 + row.1 .1 + 1) / 2 - 1;
        let b_column_mid = (column.1 .0 + column.1 .1 + 1) / 2 - 1;

        let c_mid = (n + 1) / 2 - 1;
        let mut temp_i;
        let mut temp_j;

        let c11_1 = square_matrix_multiply_recursive(
            a,
            b,
            ((row.0 .0, a_row_mid), (row.1 .0, b_row_mid)),
            ((column.0 .0, a_column_mid), (column.1 .0, b_column_mid)),
        );
        let c11_2 = square_matrix_multiply_recursive(
            a,
            b,
            ((row.0 .0, a_row_mid), (b_row_mid + 1, row.1 .1)),
            ((a_column_mid + 1, column.0 .1), (column.1 .0, b_column_mid)),
        );
        for i in 0..=c_mid {
            for j in 0..=c_mid {
                c[i][j] = c11_1[i][j] + c11_2[i][j];
            }
        }

        let c12_1 = square_matrix_multiply_recursive(
            a,
            b,
            ((row.0 .0, a_row_mid), (row.1 .0, b_row_mid)),
            ((column.0 .0, a_column_mid), (b_column_mid + 1, column.1 .1)),
        );
        let c12_2 = square_matrix_multiply_recursive(
            a,
            b,
            ((row.0 .0, a_row_mid), (b_row_mid + 1, row.1 .1)),
            (
                (a_column_mid + 1, column.0 .1),
                (b_column_mid + 1, column.1 .1),
            ),
        );
        for i in 0..=c_mid {
            for j in (c_mid + 1)..=n {
                temp_j = j - c_mid - 1;
                c[i][j] = c12_1[i][temp_j] + c12_2[i][temp_j];
            }
        }

        let c21_1 = square_matrix_multiply_recursive(
            a,
            b,
            ((a_row_mid + 1, row.0 .1), (row.1 .0, b_row_mid)),
            ((column.0 .0, a_column_mid), (column.1 .0, b_column_mid)),
        );
        let c21_2 = square_matrix_multiply_recursive(
            a,
            b,
            ((a_row_mid + 1, row.0 .1), (b_row_mid + 1, row.1 .1)),
            ((a_column_mid + 1, column.0 .1), (column.1 .0, b_column_mid)),
        );
        for i in (c_mid + 1)..=n {
            for j in 0..=c_mid {
                temp_i = i - c_mid - 1;
                c[i][j] = c21_1[temp_i][j] + c21_2[temp_i][j];
            }
        }

        let c22_1 = square_matrix_multiply_recursive(
            a,
            b,
            ((a_row_mid + 1, row.0 .1), (row.1 .0, b_row_mid)),
            ((column.0 .0, a_column_mid), (b_column_mid + 1, column.1 .1)),
        );
        let c22_2 = square_matrix_multiply_recursive(
            a,
            b,
            ((a_row_mid + 1, row.0 .1), (b_row_mid + 1, row.1 .1)),
            (
                (a_column_mid + 1, column.0 .1),
                (b_column_mid + 1, column.1 .1),
            ),
        );
        for i in (c_mid + 1)..=n {
            for j in (c_mid + 1)..=n {
                temp_i = i - c_mid - 1;
                temp_j = j - c_mid - 1;
                c[i][j] = c22_1[temp_i][temp_j] + c22_2[temp_i][temp_j];
            }
        }
        println! {"{:?}", c};
        println!("*******************************");
    }
    c
}

// 5. 矩阵乘法--Strassen 方法
// 单个矩阵不同位置求和（或求差）
fn cal(
    a: &Vec<Vec<i32>>,
    index: ((usize, usize), (usize, usize)),
    n: usize,
    sym: &str,
) -> Vec<Vec<i32>> {
    let mut c: Vec<Vec<i32>> = vec![vec![0; n]; n];
    match sym {
        "+" => {
            for i in 0..n {
                for j in 0..n {
                    c[i][j] = a[index.0 .0 + i][index.1 .0 + j] + a[index.0 .1 + i][index.1 .1 + j];
                }
            }
        }
        "-" => {
            for i in 0..n {
                for j in 0..n {
                    c[i][j] = a[index.0 .0 + i][index.1 .0 + j] - a[index.0 .1 + i][index.1 .1 + j];
                }
            }
        }
        _ => {
            println!("Other sym!");
        }
    };
    c
}

// 两个矩阵求和（或求差）
fn cal_a_and_b(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>, sym: &str) -> Vec<Vec<i32>> {
    let n = a.len();
    let mut c: Vec<Vec<i32>> = vec![vec![0; n]; n];
    match sym {
        "+" => {
            for i in 0..n {
                for j in 0..n {
                    c[i][j] = a[i][j] + b[i][j];
                }
            }
        }
        "-" => {
            for i in 0..n {
                for j in 0..n {
                    c[i][j] = a[i][j] - b[i][j];
                }
            }
        }
        _ => {
            println!("Other sym!");
        }
    };
    c
}

// 矩阵赋值
fn assign(a: &mut Vec<Vec<i32>>, b: &Vec<Vec<i32>>, index: (usize, usize)) {
    let n = b.len();
    for i in 0..n {
        for j in 0..n {
            a[index.0 + i][index.1 + j] = b[i][j];
        }
    }
}

pub fn square_matrix_multiply_strassen(a: &Vec<Vec<i32>>, b: &Vec<Vec<i32>>) -> Vec<Vec<i32>> {
    let n = a.len();
    let mut c: Vec<Vec<i32>> = vec![vec![0; n]; n];
    if n == 1 {
        c[0][0] = a[0][0] * b[0][0];
    } else {
        let mid_1 = n / 2;
        let mid_len = n / 2;

        // 构造 10 个矩阵
        // S1 = B12 - B22
        let s1 = cal(&b, ((0, mid_1), (mid_1, mid_1)), mid_len, "-");
        // S2 = A11 + A12
        let s2 = cal(&a, ((0, 0), (0, mid_1)), mid_len, "+");
        // S3 = A21 + A22
        let s3 = cal(&a, ((mid_1, mid_1), (0, mid_1)), mid_len, "+");
        // S4 = B21 - B11
        let s4 = cal(&b, ((mid_1, 0), (0, 0)), mid_len, "-");
        // S5 = A11 + A22
        let s5 = cal(&a, ((0, mid_1), (0, mid_1)), mid_len, "+");
        // S6 = B11 + B22
        let s6 = cal(&b, ((0, mid_1), (0, mid_1)), mid_len, "+");
        // S7 = A12 - A22
        let s7 = cal(&a, ((0, mid_1), (mid_1, mid_1)), mid_len, "-");
        // S8 = B21 + B22
        let s8 = cal(&b, ((mid_1, mid_1), (0, mid_1)), mid_len, "+");
        // S9 = A11 - A21
        let s9 = cal(&a, ((0, mid_1), (0, 0)), mid_len, "-");
        // S10 = B11 + B12
        let s10 = cal(&b, ((0, 0), (0, mid_1)), mid_len, "+");

        // 递归计算 7 个矩阵
        // P1 = A11 * S1
        let a11 = a[0..mid_1]
            .iter()
            .map(|x| x[0..mid_1].to_vec())
            .collect::<Vec<Vec<i32>>>();
        let p1 = square_matrix_multiply_strassen(&a11, &s1);
        // P2 = S2 * B22
        let b22 = b[mid_1..n]
            .iter()
            .map(|x| x[mid_1..n].to_vec())
            .collect::<Vec<Vec<i32>>>();
        let p2 = square_matrix_multiply_strassen(&s2, &b22);
        // P3 = S3 * B11
        let b11 = b[0..mid_1]
            .iter()
            .map(|x| x[0..mid_1].to_vec())
            .collect::<Vec<Vec<i32>>>();
        let p3 = square_matrix_multiply_strassen(&s3, &b11);
        // P4 = A22 * S4
        let a22 = a[mid_1..n]
            .iter()
            .map(|x| x[mid_1..n].to_vec())
            .collect::<Vec<Vec<i32>>>();
        let p4 = square_matrix_multiply_strassen(&a22, &s4);
        // P5 = S5 * S6
        let p5 = square_matrix_multiply_strassen(&s5, &s6);
        // P6 = S7 * S8
        let p6 = square_matrix_multiply_strassen(&s7, &s8);
        // P7 = S9 * S10
        let p7 = square_matrix_multiply_strassen(&s9, &s10);

        assign(
            &mut c,
            &cal_a_and_b(
                &cal_a_and_b(&cal_a_and_b(&p5, &p4, "+"), &p2, "-"),
                &p6,
                "+",
            ),
            (0, 0),
        );
        assign(&mut c, &cal_a_and_b(&p1, &p2, "+"), (0, mid_1));
        assign(&mut c, &cal_a_and_b(&p3, &p4, "+"), (mid_1, 0));
        assign(
            &mut c,
            &cal_a_and_b(
                &cal_a_and_b(&cal_a_and_b(&p5, &p1, "+"), &p3, "-"),
                &p7,
                "-",
            ),
            (mid_1, mid_1),
        );
    }
    c
}
